package com.tuling.code;
// 根据归并安排找出右边*2 小于当前数的个数
public class BiggerThanRightTwice {
    public static void main(String[] args) {

    }

    public int process(int [] arry,int left ,int right){
        if(left == right){ return arry[left];}

        int mid = left + ((right - left)>>1);
        return process(arry,left,mid) + process(arry,mid+1,right)
                + merge(arry,left,mid,right);
    }

    private int merge(int[] arry, int left, int mid, int right) {
        int[] help = new int[right - left + 1];

        //获取右边右多少个数 * 2 小于当前数；
        int ans = 0;
        int windowsR = mid + 1;
        for(int i = left; i<= mid;i++){
            while (windowsR < right && arry[i] > arry[windowsR] *2){
                windowsR ++;
            }
           ans += windowsR - mid -1;
        }

/**-==========================================*/
        int i = 0;
        int p1 = left;
        int p2 = right;
        while (p1 <= mid && p2 <= right){
            help[i++] = arry[p1] < arry[p2] ? arry[p1++] : arry[p2++];
        }

        while (p1 <= mid){
            help[i++] = arry[p1++];
        }
        while (p2 <= right){
            help[i++] = arry[p2++];
        }

        for (int j = 0; j < help.length; j++) {
            help[left +j] = arry[j];
        }

        return ans;
    }
}
